// 队列 + 宽搜
// N叉树的层序遍历：借助一个队列实现

// 例题 1：
// 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
// 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
//
//        示例 1：
//
//        输入：root = [1,null,3,2,4,null,5,6]
//        输出：[[1],[3,2,4],[5,6]]
//        示例 2：
//
//        输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
//        输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
//
//
//        提示：
//
//        树的高度不会超过 1000
//        树的节点总数在 [0, 104] 之间

// 解题思路：
// 借助一个队列，运用队列先进先出的特性
// 将 头/某层所有 结点放到队列中
// 每次放完一层后，将本层节点数量 size 统计出来
// 按照 size ，弹出头/某层所有 节点的时候，将其子节点放进队列中，直至队列为空

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            while(size > 0){
                Node node = queue.poll();
                tmp.add(node.val);
                for(Node child : node.children){
                    queue.offer(child);
                }
                size--;
            }
            ret.add(tmp);
        }
        return ret;
    }
}